From 5c93d072cc5d2003ed567c7f76dba92e4b2d9a69 Mon Sep 17 00:00:00 2001 From: tsteven4 <13596209+tsteven4@users.noreply.github.com> Date: Thu, 7 Jul 2022 13:19:07 -0600 Subject: [PATCH] retire qsort in favor of std::sort, std::stable_sort (#888) * replace qsort with std::sort or std::stable_sort * add test for duplicate filter using gc_data exported dates. * fix reference file permissions. * fix smplrout sort bug that shows up on macos with std::sort. the compare function has always generated incorrect values when both objects are HUGEVAL. The historic function worked with qsort everywhere, worked with std::sort on linux and windows, but failed with std::sort on macos. --- duplicate.cc | 47 ++++---------------------- duplicate.h | 7 ---- garmin_txt.cc | 24 +++++-------- reference/duplicate_exported_1.csv | 5 +++ reference/duplicate_exported_1~csv.csv | 3 ++ reference/duplicate_exported_2.csv | 5 +++ reference/duplicate_exported_2~csv.csv | 3 ++ smplrout.cc | 12 +++++-- testo.d/duplicate.test | 5 +++ 9 files changed, 47 insertions(+), 64 deletions(-) create mode 100644 reference/duplicate_exported_1.csv create mode 100644 reference/duplicate_exported_1~csv.csv create mode 100644 reference/duplicate_exported_2.csv create mode 100644 reference/duplicate_exported_2~csv.csv diff --git a/duplicate.cc b/duplicate.cc index 2cd880fda..b18296324 100644 --- a/duplicate.cc +++ b/duplicate.cc @@ -19,8 +19,8 @@ */ +#include // for stable_sort #include // for sprintf -#include // for qsort #include // for memset, strncpy #include // for QDateTime @@ -114,30 +114,6 @@ be zero so the sort will end up being an expensive no-op (expensive because, sadly, quicksort can be O(n^2) on presorted elements.) */ - -int DuplicateFilter::compare(const void* a, const void* b) -{ - const wpt_ptr* wa = (wpt_ptr*)a; - const wpt_ptr* wb = (wpt_ptr*)b; - - if (wa->wpt->gc_data->exported < wb->wpt->gc_data->exported) { - return 1; - } else if (wa->wpt->gc_data->exported > wb->wpt->gc_data->exported) { - return -1; - } - - /* If the exported dates are the same, sort by index. */ - if (wa->index < wb->index) { - return -1; - } else if (wa->index > wb->index) { - return 1; - } - - /* If index and date are the same, it's the same element. */ - return 0; - -} - void DuplicateFilter::process() { btree_node* btmp = nullptr; @@ -150,22 +126,14 @@ void DuplicateFilter::process() } dupe; Waypoint* delwpt = nullptr; - int ct = waypt_count(); - - auto* htable = (wpt_ptr*) xmalloc(ct * sizeof(wpt_ptr)); - wpt_ptr* bh = htable; + auto htable = *global_waypoint_list; - int i = 0; - foreach (Waypoint* waypointp, *global_waypoint_list) { - bh->wpt = waypointp; - bh->index = i; - i ++; - bh ++; - } - qsort(htable, ct, sizeof(*htable), compare); + auto compare_lambda = [](const Waypoint* wa, const Waypoint* wb)->bool { + return wa->gc_data->exported > wb->gc_data->exported; + }; + std::stable_sort(htable.begin(), htable.end(), compare_lambda); - for (i=0; i // for sort #include // for toupper #include // for fabs, floor #include // for NULL, snprintf, sscanf #include -#include // for atoi, abs, qsort +#include // for atoi, abs #include // for memset, strstr, strcat, strchr, strlen, strcmp, strcpy, strncpy #include // for gmtime, localtime, strftime @@ -240,15 +241,6 @@ enum_waypt_cb(const Waypoint* wpt) } -static int -sort_waypt_cb(const void* a, const void* b) -{ - const Waypoint* wa = *(Waypoint**)a; - const Waypoint* wb = *(Waypoint**)b; - return wa->shortname.compare(wb->shortname, Qt::CaseInsensitive); -} - - /* common route and track pre-work */ static void @@ -834,17 +826,19 @@ garmin_txt_write() if (waypoints > 0) { wpt_a_ct = 0; - wpt_a = (const Waypoint**)xcalloc(waypoints, sizeof(*wpt_a)); + wpt_a = new const Waypoint*[waypoints]{}; waypt_disp_all(enum_waypt_cb); route_disp_all(nullptr, nullptr, enum_waypt_cb); - qsort(wpt_a, waypoints, sizeof(*wpt_a), sort_waypt_cb); + auto sort_waypt_lambda = [](const Waypoint* wa, const Waypoint* wb)->bool { + return wa->shortname.compare(wb->shortname, Qt::CaseInsensitive) < 0; + }; + std::sort(wpt_a, wpt_a + waypoints, sort_waypt_lambda); *fout << QString::asprintf("Header\t%s\r\n\r\n", headers[waypt_header]); for (int i = 0; i < waypoints; i++) { - const Waypoint* wpt = wpt_a[i]; - write_waypt(wpt); + write_waypt(wpt_a[i]); } - xfree(wpt_a); + delete[] wpt_a; route_idx = 0; route_info = (info_t*) xcalloc(route_count(), sizeof(info_t)); diff --git a/reference/duplicate_exported_1.csv b/reference/duplicate_exported_1.csv new file mode 100644 index 000000000..4f413592a --- /dev/null +++ b/reference/duplicate_exported_1.csv @@ -0,0 +1,5 @@ +No,Latitude,Longitude,Name,Exported +1,40.0,-105.1,"zero",2015/06/24 00:00:00 +1,40.0,-105.2,"one",2015/06/25 00:00:01 +1,40.0,-105.2,"two",2015/06/25 00:00:00 +1,40.0,-105.1,"three",2015/06/24 00:00:01 diff --git a/reference/duplicate_exported_1~csv.csv b/reference/duplicate_exported_1~csv.csv new file mode 100644 index 000000000..bc70f1dfa --- /dev/null +++ b/reference/duplicate_exported_1~csv.csv @@ -0,0 +1,3 @@ +No,Latitude,Longitude,Name,Exported +1,40.000000,-105.200000,"one","2015/06/25 00:00:01" +2,40.000000,-105.100000,"three","2015/06/24 00:00:01" diff --git a/reference/duplicate_exported_2.csv b/reference/duplicate_exported_2.csv new file mode 100644 index 000000000..f3f657e9e --- /dev/null +++ b/reference/duplicate_exported_2.csv @@ -0,0 +1,5 @@ +No,Latitude,Longitude,Name,Exported +1,40.0,-105.1,"zero",2015/06/24 00:00:02 +1,40.0,-105.2,"one",2015/06/25 00:00:01 +1,40.0,-105.2,"two",2015/06/25 00:00:02 +1,40.0,-105.1,"three",2015/06/24 00:00:01 diff --git a/reference/duplicate_exported_2~csv.csv b/reference/duplicate_exported_2~csv.csv new file mode 100644 index 000000000..9bd123f45 --- /dev/null +++ b/reference/duplicate_exported_2~csv.csv @@ -0,0 +1,3 @@ +No,Latitude,Longitude,Name,Exported +1,40.000000,-105.100000,"zero","2015/06/24 00:00:02" +2,40.000000,-105.200000,"two","2015/06/25 00:00:02" diff --git a/smplrout.cc b/smplrout.cc index 500f3198c..1a4814f73 100644 --- a/smplrout.cc +++ b/smplrout.cc @@ -56,7 +56,8 @@ 2008/08/20: added "relative" option, (Carsten Allefeld, carsten.allefeld@googlemail.com) */ -#include // for qsort, strtol +#include // for sort +#include // for strtol #include // for swap #include // for QDateTime @@ -158,6 +159,9 @@ int SimplifyRouteFilter::compare_xte(const void* a, const void* b) const auto* xte_b = static_cast(b); if (HUGEVAL == xte_a->distance) { + if (HUGEVAL == xte_b->distance) { + return 0; + } return -1; } @@ -238,7 +242,11 @@ void SimplifyRouteFilter::routesimple_tail(const route_head* rte) /* sort XTE array, lowest XTE last */ - qsort(xte_recs, xte_count, sizeof(struct xte), compare_xte); + auto compare_xte_lambda = [](const xte& a, const xte& b)->bool { + return compare_xte(&a, &b) < 0; + }; + std::sort(xte_recs, xte_recs + xte_count, compare_xte_lambda); + for (i = 0; i < xte_count; i++) { xte_recs[i].intermed->xte_rec = xte_recs+i; diff --git a/testo.d/duplicate.test b/testo.d/duplicate.test index c6dad28ab..ff8aaa5e4 100644 --- a/testo.d/duplicate.test +++ b/testo.d/duplicate.test @@ -7,3 +7,8 @@ gpsbabel -i geo -f ${REFERENCE}/geocaching.loc -o csv -F ${TMPDIR}/filterdupe.cs gpsbabel -i geo -f ${REFERENCE}/geocaching.loc -f ${REFERENCE}/geocaching.loc -x duplicate,shortname \ -o csv -F ${TMPDIR}/filterdupe.csv2 sort_and_compare ${TMPDIR}/filterdupe.csv1 ${TMPDIR}/filterdupe.csv2 + +gpsbabel -i unicsv,utc -f ${REFERENCE}/duplicate_exported_1.csv -x duplicate,location -o unicsv,utc -F ${TMPDIR}/duplicate_exported_1~csv.csv +compare ${REFERENCE}/duplicate_exported_1~csv.csv ${TMPDIR}/duplicate_exported_1~csv.csv +gpsbabel -i unicsv,utc -f ${REFERENCE}/duplicate_exported_2.csv -x duplicate,location -o unicsv,utc -F ${TMPDIR}/duplicate_exported_2~csv.csv +compare ${REFERENCE}/duplicate_exported_2~csv.csv ${TMPDIR}/duplicate_exported_2~csv.csv -- 2.30.2